package myString;

class LinkNode            //链串结点类型
{
    char data;            //存放一个字符
    LinkNode next;        //指向下一个结点的指针

    public LinkNode()        //构造方法
    {
        next = null;
    }

    public LinkNode(char ch)    //重载构造方法
    {
        data = ch;
        next = null;
    }
}

public class MyLinkedString {
    LinkNode head;
    int size;            //串中字符个数
    String ss;

    public MyLinkedString()    //构造方法
    {
        head = new LinkNode();    //建立头结点
        size = 0;
    }
    //串的基本运算算法

    public MyLinkedString InsStr(int i, MyLinkedString t)  //串插入
    {
        MyLinkedString s = new MyLinkedString();
        if (i < 0 || i > size)        //参数不正确时返回空串
            return s;
        LinkNode p = head.next, p1 = t.head.next, q, r;
        r = s.head;            //r指向新建链表的尾结点
        for (int k = 0; k < i; k++)    //将当前链串的前i个结点复制到s
        {
            q = new LinkNode(p.data);
            r.next = q;
            r = q;        //将q结点插入到尾部
            p = p.next;
        }
        while (p1 != null)        //将t中所有结点复制到s
        {
            q = new LinkNode(p1.data);
            r.next = q;
            r = q;        //将q结点插入到尾部
            p1 = p1.next;
        }
        while (p != null)        //将p及其后的结点复制到s
        {
            q = new LinkNode(p.data);
            r.next = q;
            r = q;        //将q结点插入到尾部
            p = p.next;
        }
        s.size = size + t.size;
        r.next = null;            //尾结点的next置为空
        return s;            //返回新建的链串
    }

}
